#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//class Solution {
//public:
//    int threeSumClosest(vector<int>& nums, int target) {
//        sort(nums.begin(), nums.end());
//        int i = nums.size() - 1;
//        int sum = nums[0] + nums[1] + nums[2];
//        while (i > 1)
//        {
//            int left = 0;
//            int right = i - 1;
//            while (left < right)
//            {
//                if (abs(nums[left] + nums[right] + nums[i] - target) < abs(sum - target))
//                {
//                    sum = nums[left] + nums[right] + nums[i];
//                }
//                if (nums[left] + nums[right] + nums[i] > target)
//                {
//                    right--;
//                }
//                else if (nums[left] + nums[right] + nums[i] < target)
//                {
//                    left++;
//                }
//                else
//                {
//                    return nums[left] + nums[right] + nums[i];
//                }
//            }
//            i--;
//        }
//        return sum;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target) {
//        int n = nums.size();
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//        int i = 0;
//        while (i < n - 3)
//        {
//            long long sum = target - nums[i];
//            int left = i + 1;
//            while (left < n - 2)
//            {
//                int right = n - 1;
//                int mid = left + 1;
//                while (mid < right)
//                {
//                    if ((long long)nums[left] + nums[mid] + nums[right] < sum)
//                    {
//                        mid++;
//                    }
//                    else if ((long long)nums[left] + nums[mid] + nums[right] > sum)
//                    {
//                        right--;
//                    }
//                    else
//                    {
//                        vector<int> v;
//                        v.push_back(nums[i]);
//                        v.push_back(nums[left]);
//                        v.push_back(nums[mid]);
//                        v.push_back(nums[right]);
//                        ret.push_back(v);
//                        while (mid < right && nums[mid] == nums[mid + 1])
//                        {
//                            mid++;
//                        }
//                        mid++;
//                    }
//                }
//                left++;
//                while (left < n - 2 && nums[left] == nums[left - 1])
//                {
//                    left++;
//                }
//            }
//            i++;
//            while (i < n - 3 && nums[i - 1] == nums[i])
//            {
//                i++;
//            }
//        }
//        return ret;
//    }
//};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int i = nums.size() - 1;
        while (i > 2)
        {
            long long p = target - nums[i];
            int k = i - 1;
            while (k > 1)
            {
                int left = 0;
                int right = k - 1;
                while (left < right)
                {
                    if ((long long)nums[left] + nums[right] + nums[k] == p)
                    {
                        ret.push_back({ nums[left],nums[right],nums[k],nums[i] });
                        while (right > left && nums[right] == nums[right - 1])
                        {
                            right--;
                        }
                        right--;
                    }
                    else if ((long long)nums[left] + nums[right] + nums[k] < p)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
                while (k > 1 && nums[k] == nums[k - 1])
                {
                    k--;
                }
                k--;
            }
            while (i > 2 && nums[i - 1] == nums[i])
            {
                i--;
            }
            i--;
        }
        return ret;
    }
};
int main()
{
    vector<int> num = { 1,0,-1,0,-2,2 };
    Solution s;
    vector<vector<int>> ret = s.fourSum(num, 0);
    for (int x = 0; x < ret.size(); x++)
    {
        for (int y = 0; y < ret[x].size(); y++)
        {
            cout << ret[x][y] << " ";
        }
        cout << endl;
    }
    return 0;
}

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        int fast = 0;
        int slow = 0;
        int sum = 0;
        int my_min = INT_MAX;
        while (fast < n)
        {
            sum += nums[fast];
            while (sum >= target)
            {
                my_min = min(my_min, fast - slow + 1);
                sum -= nums[slow++];
            }
            fast++;
        }
        if (my_min == INT_MAX)
        {
            return 0;
        }
        return my_min;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
        {
            return 0;
        }
        int min = INT_MAX;
        int slow = 0;
        int fast = 0;
        int len = 0;
        int sum = 0;
        while (fast < n)
        {
            if (sum < target)
            {
                sum += nums[fast];
                fast++;
                len++;
            }
            while (sum >= target)
            {
                if (len < min)
                {
                    min = len;
                }
                sum -= nums[slow++];
                len--;
            }
        }
        if (min == INT_MAX)
        {
            return 0;
        }
        return min;
    }
};
